package dfs;

public class _04n皇后问题 {
    /**
     * 请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个n*n的棋盘上放置n个棋子，
     * 使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。
     * 给定一个int n，请返回方法数，保证n小于等于15
     */
    static int n;
    static int[] rec;
    static int cnt;

    public static void main(String[] args) {
        n = 4;
        rec = new int[4];
        dfs(0);
        System.out.println(cnt);
    }

    public static void dfs(int row) {
        if (row == n) {
            cnt++;
            return;
        }
        for (int col = 0; col < n; col++) {
            boolean ok = true;
            //检查这个皇后和以前放过的皇后是否有冲突
            for (int i = 0; i < row; i++) {
                if (rec[i] == col || i + rec[i] == row + col || rec[i] - i == col - row) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                rec[row] = col;
                dfs(row + 1);
            }
        }

    }
}
